#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
typedef pair<int,int> pii;
const int N=110,M=2010;
int n,m;
int w[M];
int dis[N];
bool st[N];
int ans=1e9+7;
int h[N],idx=0;
struct Node{
	int w;
	int to,ne;
}tr[M<<1];
void add(int u,int v,int w){
	tr[idx].w=w,tr[idx].to=v,tr[idx].ne=h[u],h[u]=idx++;
}
void dij(int p){
	priority_queue<pii> q;
	memset(st,false,sizeof st);
	memset(dis,0x3f,sizeof dis);
	int inf=dis[0];
	dis[1]=0,q.push({0,1});
	while(!q.empty()){
		int t=q.top().y;
		q.pop();
		if(st[t]) continue;
		st[t]=true;
		for(int i=h[t];i!=-1;i=tr[i].ne){
			int to=tr[i].to;
			if(dis[to]>dis[t]+tr[i].w&&tr[i].w<=p){
				dis[to]=dis[t]+tr[i].w;
				q.push({-dis[to],to});
			}
		}
	}
	if(dis[n]!=inf) ans=min(ans,dis[n]+p);
}
signed main(){
	memset(h,-1,sizeof h);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v>>w[i];
		add(u,v,w[i]),add(v,u,w[i]);
	}
	for(int i=1;i<=m;i++) dij(w[i]);
	cout<<ans<<endl;
	return 0;
}